package com.wangzemin.leetcode.num673;

public class Solution {
    public int findNumberOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int[] maxLit = new int[nums.length];
        int[] maxLitCount = new int[nums.length];
        maxLit[0] = 1;
        maxLitCount[0] = 1;

        int globalMaxLit = 1;
        int globalMaxLitCount = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    int val = maxLit[j] + 1;
                    if (val > maxLit[i]) {
                        maxLit[i] = val;
                        maxLitCount[i] = maxLitCount[j];
                    } else if (val == maxLit[i]) {
                        maxLitCount[i]=maxLitCount[i]+maxLitCount[j];
                    }
                } else if (maxLit[i] < 1) {
                    maxLit[i] = 1;
                    maxLitCount[i] = 1;
                }
            }
            if (globalMaxLit < maxLit[i]) {
                globalMaxLit = maxLit[i];
                globalMaxLitCount = maxLitCount[i];
            } else if (globalMaxLit == maxLit[i]) {
                globalMaxLitCount = globalMaxLitCount + maxLitCount[i];
            }
        }
        return globalMaxLitCount;
    }

//        public static void main(String[] args){
//        Solution solution = new Solution();
////        System.out.println(solution.findNumberOfLIS(new int[]{1,3,5,4,7}));
//        System.out.println(solution.findNumberOfLIS(new int[]{1,2,4,3,5,4,7,2}));
//    }
}